SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Deterministic algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Deterministic algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Idempotency" class="mw-redirect" title="Idempotency">Idempotency</a>.</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>deterministic algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.

</p><p>Formally, a deterministic algorithm computes a <a href="Function_(mathematics)" title="Function (mathematics)">mathematical function</a>; a function has a unique value for any input in its <a href="Function_domain" class="mw-redirect" title="Function domain">domain</a>, and the algorithm is a process that produces this particular value as output.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

<p>Deterministic algorithms can be defined in terms of a <a href="State_machine" class="mw-redirect" title="State machine">state machine</a>: a <i>state</i> describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its <i>initial state</i> or <i>start state</i>. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.

</p><p>Examples of particular <a href="Abstract_machine" title="Abstract machine">abstract machines</a> which are deterministic include the <a href="Deterministic_Turing_machine" class="mw-redirect" title="Deterministic Turing machine">deterministic Turing machine</a> and <a href="Deterministic_finite_automaton" title="Deterministic finite automaton">deterministic finite automaton</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Non-deterministic_algorithms">Non-deterministic algorithms</h2></div>

<p>A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:

</p>

<ul><li>If it uses an external state other than the input, such as user input, a <a href="Global_variable" title="Global variable">global variable</a>, a hardware timer value, a <a href="Randomness" title="Randomness">random</a> value, or stored disk data.</li>

<li>If it operates in a way that is timing-sensitive, for example, if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.</li>

<li>If a hardware error causes its state to change in an unexpected way.</li></ul>

<p>Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most <a href="Programming_language" title="Programming language">programming languages</a> and especially <a href="Functional_programming" title="Functional programming">functional programming</a> languages make an effort to prevent the above events from happening except under controlled conditions.

</p><p>The prevalence of <a href="Multi-core_processor" title="Multi-core processor">multi-core processors</a> has resulted in a surge of interest in determinism in parallel programming and challenges of non-determinism have been well documented.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> A number of tools to help deal with the challenges have been proposed<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> to deal with <a href="Deadlock_(computer_science)" title="Deadlock (computer science)">deadlocks</a> and <a href="Race_condition" title="Race condition">race conditions</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Disadvantages_of_determinism">Disadvantages of determinism</h2></div>

<p>It is advantageous, in some cases, for a program to exhibit nondeterministic behavior. The behavior of a card shuffling program used in a game of <a href="Blackjack" title="Blackjack">blackjack</a>, for example, should not be predictable by players — even if the source code of the program is visible. The use of a <a href="Pseudorandom_number_generator" title="Pseudorandom number generator">pseudorandom number generator</a> is often not sufficient to ensure that players are unable to predict the outcome of a shuffle. A clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold 'em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> These problems can be avoided, in part, through the use of a <a href="Cryptographically_secure_pseudo-random_number_generator" class="mw-redirect" title="Cryptographically secure pseudo-random number generator">cryptographically secure pseudo-random number generator</a>, but it is still necessary for an unpredictable <a href="Random_seed" title="Random seed">random seed</a> to be used to initialize the generator. For this purpose, a source of nondeterminism is required, such as that provided by a <a href="Hardware_random_number_generator" title="Hardware random number generator">hardware random number generator</a>.

</p><p>Note that a negative answer to the <a href="P%3DNP_problem" class="mw-redirect" title="P=NP problem">P=NP problem</a> would not imply that programs with nondeterministic output are theoretically more powerful than those with deterministic output. The complexity class <a href="NP_(complexity)" title="NP (complexity)">NP (complexity)</a> can be defined without any reference to nondeterminism using the <a href="NP_(complexity)" title="NP (complexity)">verifier-based definition</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Determinism_categories_in_languages">Determinism categories in languages</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Mercury">Mercury</h3></div>

<p>The <a href="Mercury_(programming_language)" title="Mercury (programming language)">mercury</a> logic-functional programming language establishes different determinism categories for predicate modes as explained in the reference.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Haskell">Haskell</h3></div>

<p><a href="Haskell" title="Haskell">Haskell</a> provides several mechanisms:

</p>

<ul><li>Non-determinism or notion of Fail

<ul><li>the <i>Maybe</i> and <i>Either</i> types include the notion of success in the result.</li>

<li>the <i>fail</i> method of the class Monad, may be used to signal <i>fail</i> as exception.</li>

<li>the Maybe <a href="Monad_(functional_programming)" title="Monad (functional programming)">monad</a> and MaybeT monad transformer provide for failed computations (stop the computation sequence and return Nothing)<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li></ul></li>

<li>Neterminism/non-det with multiple solutions

<ul><li>you may retrieve all possible outcomes of a multiple result computation, by wrapping its result type in a MonadPlus <a href="Monad_(functional_programming)" title="Monad (functional programming)">monad</a>. (its method <i>mzero</i> makes an outcome fail and <i>mplus</i> collects the successful results).<sup id="cite_ref-monad-plus_11-0" class="reference"><a href="#cite_note-monad-plus-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li></ul></li></ul>

<div class="mw-heading mw-heading3"><h3 id="ML_family_and_derived_languages">ML family and derived languages</h3></div>

<p>As seen in <a href="Standard_ML" title="Standard ML">Standard ML</a>, <a href="OCaml" title="OCaml">OCaml</a> and <a href="Scala_(programming_language)" title="Scala (programming language)">Scala</a>

</p>

<ul><li>The <i>option</i> type includes the notion of success.</li></ul>

<p>In <a href="Java_(programming_language)" title="Java (programming language)">Java</a>, the <i>null</i> reference value may represent an unsuccessful (out-of-domain) result.

</p>

<ul><li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFEdward_A._Lee" class="citation web cs1">Edward A. Lee. <a rel="nofollow" class="external text" href="http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf">"The Problem with Threads"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-29</span></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFBocchino_Jr.AdveAdveSnir2009" class="citation conference cs1">Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). <a rel="nofollow" class="external text" href="https://www.usenix.org/legacy/event/hotpar09/tech/full_papers/bocchino/bocchino_html/"><i>Parallel Programming Must Be Deterministic by Default</i></a>. <a href="USENIX" title="USENIX">USENIX</a> Workshop on Hot Topics in Parallelism.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/">"Intel Parallel Inspector Thread Checker"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-29</span></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFYuan_Lin" class="citation web cs1">Yuan Lin. <a rel="nofollow" class="external text" href="http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf">"Data Race and Deadlock Detection with Sun Studio Thread Analyzer"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-29</span></span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFIntel" class="citation web cs1">Intel. <a rel="nofollow" class="external text" href="http://software.intel.com/en-us/intel-parallel-inspector">"Intel Parallel Inspector"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-29</span></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFDavid_Worthington" class="citation web cs1">David Worthington. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090528030044/http://www.sdtimes.com/link/33497">"Intel addresses development life cycle with Parallel Studio"</a>. Archived from <a rel="nofollow" class="external text" href="http://sdtimes.com/link/33497">the original</a> on 2009-05-28<span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-26</span></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFMcGrawViega" class="citation web cs1"><a href="Gary_McGraw" title="Gary McGraw">McGraw, Gary</a>; <a href="John_Viega" title="John Viega">Viega, John</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20080313043638/http://www.ibm.com/developerworks/library/s-playing/#h4">"Make your software behave: Playing the numbers: How to cheat in online gambling"</a>. <i><a href="IBM" title="IBM">IBM</a></i>. Archived from <a rel="nofollow" class="external text" href="http://www.ibm.com/developerworks/library/s-playing/#h4">the original</a> on 2008-03-13<span class="reference-accessdate">. Retrieved <span class="nowrap">2007-07-02</span></span>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120703001434/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html#Determinism-categories">"Determinism categories in the Mercury programming language"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html">the original</a> on 2012-07-03<span class="reference-accessdate">. Retrieved <span class="nowrap">2013-02-23</span></span>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120703001411/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html#Predicate-and-function-mode-declarations">"Mercury predicate modes"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html">the original</a> on 2012-07-03<span class="reference-accessdate">. Retrieved <span class="nowrap">2013-02-25</span></span>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.haskell.org/haskellwiki/Monad#Common_monads">"Representing failure using the Maybe monad"</a>.</cite></span>

</li>

<li id="cite_note-monad-plus-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-monad-plus_11-0">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.haskell.org/haskellwiki/MonadPlus">"The class MonadPlus"</a>.</cite></span>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-03" href="https://en.wikipedia.org/wiki/?title=Deterministic_algorithm&oldid=1293713463">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>